using System;
using System.Collections.Generic;
using System.Linq;

namespace TTEngine.TTMath
{
    public class MaxRectsBin
    {
        private const int EDGE_MAX_VALUE = 4096;
        private List<SizeRect> _freeRects = new List<SizeRect>();
        private List<SizeRect> _rects = new List<SizeRect>();
        private bool _verticalExpand = false;
        private SizeRect _stage;
        private int _border;
        private int _padding;

        public int Width { get; private set; }
        public int Height { get; private set; }
        public int MaxWidth { get; private set; }
        public int MaxHeight { get; private set; }
        public PackingOptions Options { get; private set; }
        public string Tag { get; set; }

        public MaxRectsBin(int maxWidth = EDGE_MAX_VALUE, int maxHeight = EDGE_MAX_VALUE, int padding = 0, PackingOptions options = null)
        {
            MaxWidth = maxWidth;
            MaxHeight = maxHeight;
            _padding = padding;
            Options = options ?? new PackingOptions();
            Width = Options.Smart ? 0 : maxWidth;
            Height = Options.Smart ? 0 : maxHeight;
            _border = Options.Border;
            _stage = new SizeRect(Width, Height);

            _freeRects.Add(new SizeRect(
                MaxWidth + _padding - _border * 2,
                MaxHeight + _padding - _border * 2,
                _border,
                _border));
        }

        public SizeRect? Add(SizeRect rect)
        {
            if (rect.Width > MaxWidth || rect.Height > MaxHeight)
                return null;

            var node = FindNode(rect.Width, rect.Height, Options.AllowRotation);
            if (node.HasValue)
            {
                UpdateBinSize(node.Value);
                int numRectToProcess = _freeRects.Count;
                int i = 0;
                while (i < numRectToProcess)
                {
                    if (SplitNode(_freeRects[i], node.Value))
                    {
                        _freeRects.RemoveAt(i);
                        numRectToProcess--;
                        i--;
                    }
                    i++;
                }
                PruneFreeList();
                _verticalExpand = Width > Height;
                rect.X = node.Value.X;
                rect.Y = node.Value.Y;
                _rects.Add(rect);
                return rect;
            }
            else if (!_verticalExpand)
            {
                if (UpdateBinSize(new SizeRect(
                    rect.Width + _padding, rect.Height + _padding,
                    Width + _padding - _border, _border)) ||
                    UpdateBinSize(new SizeRect(
                        rect.Width + _padding, rect.Height + _padding,
                        _border, Height + _padding - _border)))
                {
                    return Add(rect);
                }
            }
            else
            {
                if (UpdateBinSize(new SizeRect(
                    rect.Width + _padding, rect.Height + _padding,
                    _border, Height + _padding - _border)) ||
                    UpdateBinSize(new SizeRect(
                        rect.Width + _padding, rect.Height + _padding,
                        Width + _padding - _border, _border)))
                {
                    return Add(rect);
                }
            }
           return null;
        }

        private SizeRect? FindNode(int width, int height, bool allowRotation)
        {
            float score = float.MaxValue;
            SizeRect? bestNode = null;

            foreach (var freeRect in _freeRects)
            {
                if (freeRect.Width >= width && freeRect.Height >= height)
                {
                    float areaFit = Options.Logic == PackingLogic.MaxArea ?
                        freeRect.Width * freeRect.Height - width * height :
                        System.Math.Min(freeRect.Width - width, freeRect.Height - height);

                    if (areaFit < score)
                    {
                        bestNode = new SizeRect(width, height, freeRect.X, freeRect.Y);
                        score = areaFit;
                    }
                }

                if (!allowRotation) continue;

                if (freeRect.Width >= height && freeRect.Height >= width)
                {
                    float areaFit = Options.Logic == PackingLogic.MaxArea ?
                        freeRect.Width * freeRect.Height - height * width :
                        System.Math.Min(freeRect.Height - width, freeRect.Width - height);

                    if (areaFit < score)
                    {
                        bestNode = new SizeRect(height, width, freeRect.X, freeRect.Y);
                        score = areaFit;
                    }
                }
            }

            return bestNode;
        }

        private bool SplitNode(SizeRect freeRect, SizeRect usedNode)
        {
            if (!freeRect.Intersects(usedNode))
                return false;

            if (usedNode.X < freeRect.X + freeRect.Width && usedNode.X + usedNode.Width > freeRect.X)
            {
                if (usedNode.Y > freeRect.Y && usedNode.Y < freeRect.Y + freeRect.Height)
                {
                    _freeRects.Add(new SizeRect(
                        freeRect.Width,
                        usedNode.Y - freeRect.Y,
                        freeRect.X,
                        freeRect.Y));
                }

                if (usedNode.Y + usedNode.Height < freeRect.Y + freeRect.Height)
                {
                    _freeRects.Add(new SizeRect(
                        freeRect.Width,
                        freeRect.Y + freeRect.Height - (usedNode.Y + usedNode.Height),
                        freeRect.X,
                        usedNode.Y + usedNode.Height));
                }
            }

            if (usedNode.Y < freeRect.Y + freeRect.Height && usedNode.Y + usedNode.Height > freeRect.Y)
            {
                if (usedNode.X > freeRect.X && usedNode.X < freeRect.X + freeRect.Width)
                {
                    _freeRects.Add(new SizeRect(
                        usedNode.X - freeRect.X,
                        freeRect.Height,
                        freeRect.X,
                        freeRect.Y));
                }

                if (usedNode.X + usedNode.Width < freeRect.X + freeRect.Width)
                {
                    _freeRects.Add(new SizeRect(
                        freeRect.X + freeRect.Width - (usedNode.X + usedNode.Width),
                        freeRect.Height,
                        usedNode.X + usedNode.Width,
                        freeRect.Y));
                }
            }

            return true;
        }

        private void PruneFreeList()
        {
            for (int i = 0; i < _freeRects.Count; i++)
            {
                for (int j = i + 1; j < _freeRects.Count; j++)
                {
                    if (_freeRects[j].Contains(_freeRects[i]))
                    {
                        _freeRects.RemoveAt(i);
                        i--;
                        break;
                    }
                    if (_freeRects[i].Contains(_freeRects[j]))
                    {
                        _freeRects.RemoveAt(j);
                        j--;
                    }
                }
            }
        }

        private bool UpdateBinSize(SizeRect node)
        {
            if (!Options.Smart) return false;
            if (_stage.Contains(node)) return false;

            int tmpWidth = System.Math.Max(Width, node.X + node.Width - _padding + _border);
            int tmpHeight = System.Math.Max(Height, node.Y + node.Height - _padding + _border);

            if (Options.AllowRotation)
            {
                int rotWidth = System.Math.Max(Width, node.X + node.Height - _padding + _border);
                int rotHeight = System.Math.Max(Height, node.Y + node.Width - _padding + _border);
                if (rotWidth * rotHeight < tmpWidth * tmpHeight)
                {
                    tmpWidth = rotWidth;
                    tmpHeight = rotHeight;
                }
            }

            if (Options.Pot)
            {
                double log2e = 1.0 / System.Math.Log(2);
                tmpWidth = (int)System.Math.Pow(2, System.Math.Ceiling(System.Math.Log(tmpWidth) * log2e));
                tmpHeight = (int)System.Math.Pow(2, System.Math.Ceiling(System.Math.Log(tmpHeight) * log2e));
            }

            if (Options.Square)
            {
                tmpWidth = tmpHeight = System.Math.Max(tmpWidth, tmpHeight);
            }

            if (tmpWidth > MaxWidth + _padding || tmpHeight > MaxHeight + _padding)
                return false;

            ExpandFreeRects(tmpWidth + _padding, tmpHeight + _padding);
            Width = _stage.Width = tmpWidth;
            Height = _stage.Height = tmpHeight;
            return true;
        }

        private void ExpandFreeRects(int width, int height)
        {
            for (int i = 0; i < _freeRects.Count; i++)
            {
                var rect = _freeRects[i];
                var maxWidth = System.Math.Min(Width + _padding - _border, width);
                var maxHeight = System.Math.Min(Height + _padding - _border, height);

                if (rect.X + rect.Width >= maxWidth)
                {
                    _freeRects[i] = new SizeRect(
                        width - rect.X - _border,
                        rect.Height,
                        rect.X,
                        rect.Y);
                }
                if (rect.Y + rect.Height >= maxHeight)
                {
                    _freeRects[i] = new SizeRect(
                        rect.Width,
                        height - rect.Y - _border,
                        rect.X,
                        rect.Y);
                }
            }

            _freeRects.Add(new SizeRect(
                width - Width - _padding,
                height - _border * 2,
                Width + _padding - _border,
                _border));

            _freeRects.Add(new SizeRect(
                width - _border * 2,
                height - Height - _padding,
                _border,
                Height + _padding - _border));

            _freeRects.RemoveAll(freeRect =>
                freeRect.Width <= 0 || freeRect.Height <= 0 ||
                freeRect.X < _border || freeRect.Y < _border);

            PruneFreeList();
        }

        public void Reset(bool deepReset = false)
        {
            if (deepReset)
            {
                _rects.Clear();
                Options = new PackingOptions();
            }

            Width = Options.Smart ? 0 : MaxWidth;
            Height = Options.Smart ? 0 : MaxHeight;
            _border = Options.Border;
            _freeRects.Clear();
            _freeRects.Add(new SizeRect(
                MaxWidth + _padding - _border * 2,
                MaxHeight + _padding - _border * 2,
                _border,
                _border));
            _stage = new SizeRect(Width, Height);
        }

        public List<SizeRect> Repack()
        {
            List<SizeRect> unpacked = new List<SizeRect>();
            Reset();

            _rects.Sort((a, b) =>
            {
                float result = System.Math.Max(b.Width, b.Height) - System.Math.Max(a.Width, a.Height);
                return result == 0 ? 0 : (result > 0 ? 1 : -1);
            });

            foreach (var rect in _rects.ToList())
            {
                if (Add(rect)==null)
                {
                    unpacked.Add(rect);
                    _rects.Remove(rect);
                }
            }

            return unpacked;
        }
    }
} 